package hot100;


/*
 * Author：江松
 * Date：2023/4/15 10:27
 *
 *
 最长回文子串：
 1，暴力O(n*n*2)——中心扩展法
 题解：
 2，动态规划（区间DP）
 子结构，小的如果是回文，并且相邻两边相同，则大的也是回文
 f(i,j)表示i~j是否为回文串
 转移f(i,j)=f(i+1,j-1)^s[i-1]==s[j+1],长度<4时（长度为2,3是直接由si,sj决定）
 注意计算顺序和边界

 3，Manacher算法(不作为面试内容)

 */

public class Main5 {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n == 0) return "";
        boolean dp[][] = new boolean[n][n];

        int st = 0, mlen = 1;
        //初始化
        for (int i = 0; i < n; ++i) dp[i][i] = true;

        //枚举区间长度
        for(int len=2;len<=n;++len){
            //枚举左点
            for(int i=0;i<n;++i){
                int j=i+len-1;
                if(j>=n)break;

                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j]=dp[i+1][j-1];
                    if(j-i+1<4){
                        dp[i][j]=true;
                    }
                }else{
                    dp[i][j]=false;
                }

                if(len>mlen){
                    mlen=len;
                    st=i;
                }
            }
        }
        return s.substring(st,st+mlen);
    }

    /*
    //动态规划计算顺序？
    public String longestPalindrome(String s) {
        int n=s.length();
        if(n==0)return "";
        boolean dp[][]=new boolean[n][n];

        int st=0,len=0;
        //初始化
        for(int i=0;i<n;++i)dp[i][i]=true;
        //计算,i表示左端点，j表示右端点
        for(int i=n-1;i>=0;--i){
            for(int j=i+1;j<n;++j){
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j]=dp[i+1][j-1];
                    if(j-i+1<4)dp[i][j]=true;
                }else{
                    dp[i][j]=false;
                }
                if(i-j+1>len&&dp[i][j]){
                    st=i;
                    len=i-j+1;
                }
            }
        }
        return s.substring(st,st+len);
    }
    */



    /*
    public String longestPalindrome(String s) {
        String res="";
        int mlen=-1;
        for(int i=0;i<s.length();++i){
            for(int j=0;j<2;++j){
                int l=i;
                int r=i+j;
                while (l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){
                    l--;
                    r++;
                }
                //l!=r,r-l+1-2
                if(r-l-1>mlen){
                    mlen=r-l-1;
                    res=s.substring(l+1,r);//左闭右开
                }
            }
        }
        return res;
    }
    */
}
